package com.webxiaohua.algorithm.sort;

import java.util.Random;

/**
 * @author shenxinhua
 * @date 2019-06-22 17:40
 * @desc 快速排序
 */
public class QuickSort {
    /**
     * @desc 生成数组
     * @param length
     * @return
     */
    public static int[] generateArray(int length){
        int[] array = new int[length];
        Random random = new Random();
        for(int i=0;i<array.length;i++){
            array[i] = random.nextInt(1000);
        }
        return array;
    }

    /**
     * @desc 快速排序 （基本思想是分治，对于一组给定的数组，将原序列分为两部分，
     * 其中前一部分的记录比后一部分的所有记录都要小，然后再依次对前后两部分的数据进行排序，
     * 递归该过程，直到数组中所有的数据有序为止）
     * @param array 数组
     * @param low 左侧位置
     * @param high 右侧位置
     */
    public static void sort(int[] array, int low, int high) {
        if(low > high){
            return;
        }
        int i = low; // 左边的哨兵
        int j = high; // 右边的哨兵
        int tmp = array[low]; // 以左边位基准位
        while(i < j){
            // 先从右边往左找到一个小于基数的数
            // 当右边哨兵找到的数大于基数时，继续查找 （j-1 不跳出循环）
            // 找到后跳出循环
            while(tmp <= array[j] && i < j){
                j--;
            }
            // 再看左边，从左往右找到一个大于基数的数
            // 当左边哨兵找到的数小于基数时，继续查找 （i+1 不跳出循环）
            // 找到后跳出循环
            while (tmp >= array[i] && i<j){
                i++;
            }
            // 满足条件则进行交换
            if(i<j){
                int x = array[i];
                int y = array[j];
                array[i] = y;
                array[j] = x;
            }
        }
        // 此时跳出了循环，说明 i==j 左右在同一位置
        array[low] = array[i];
        array[i] = tmp;
        // 这时 左边数组 < i < 右边数组，只需要递归左右数组排序即可
        sort(array,low,j-1);
        sort(array,j+1,high);
    }

    public static void main(String... args){
        int[] array = generateArray(10);
        System.out.println("排序前：");
        for(int i:array){
            System.out.println(i);
        }
        sort(array,0,array.length-1);
        System.out.println("--------------- 排序完成： ---------------");
        for(int i:array){
            System.out.println(i);
        }
    }
}
